Internet Info 1994 March/Internet Info CD-ROM (Walnut Creek) (March 1994).iso/inet/internet-drafts/draft-rekhter-select-providers-00.txt

Text File | 1993-09-27 | 13KB | 394 lines

                           - 1 -



Network Working Group                                      Y. Rekhter
INTERNET DRAFT                 T.J. Watson Research Center, IBM Corp.
                                                       September 1993


                     Selecting an Indirect Provider


Status of this Memo


   This document is an Internet Draft.  Internet Drafts are working
   documents of the Internet Engineering Task Force (IETF), its Areas,
   and its Working Groups.  Note that other groups may also distribute
   working documents as Internet Drafts.

   Internet Drafts are draft documents valid for a maximum of six
   months.  Internet Drafts may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a
   ``working draft'' or ``work in progress.''

   Please check the 1id-abstracts.txt listing contained in the
   internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net,
   nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the
   current status of any Internet Draft.



1 Introduction


   The Border Gateway Protocol (BGP) [1] and Inter-Domain Routing
   Protocol (IDRP) [2] are two similar protocols that can be used for
   inter-domain routing.  It was asserted that not all routing policies
   can be supported with these protocols. Specifically, as stated in
   [1], "BGP does not enable one AS to send traffic to a neighboring AS
   intending that the traffic take a different route from that taken by
   traffic originating in the neighboring AS". In this document we
   describe a simple approach to remove this limitation from BGP and
   IDRP. The proposed scheme can be realised with the existing
   technology and off-the shelf components and doesn't require any new
   routing protocols.







Expiration Date March 1994                                      [Page 1]

                           - 2 -



2 Background


   The Internet is viewed as a set of arbitrary interconnected
   Autonomous Systems (Domains). An autonomous system that carries
   transit traffic is called a service provider (or just a provider). An
   autonomous system that uses other autonomous system(s) to carry
   locally originated traffic is called a service subscriber (or just a
   subscriber). A provider that has an external neighbor (in the
   BGP/IDRP sense) with one of the BGP/IDRP speakers within a subscriber
   is called the direct provider (with respect to the subscriber).  All
   other providers are called indirect (with respect to the subscriber).

   Within the current model (see [1]) BGP/IDRP limits the choice of
   routes available to a subscriber to the routes selected by all of its
   direct providers.  A route available to a direct provider, but not
   selected by the provider can't be made available to the subscriber.

   As an illustration of this limitation consider the following topology
   (the example is taken from [3]):


                  D       B
                   \     / \
                    \   /   \
                     \ /     \
                      C       A
                     / \      /
                    /   \    /
                   /     \  /
                  /       \/
                 F         E


   where A, B, C, D, E, and F are autonomous systems. C has to select
   between B and E as the next hop domain to destinations in A.
   Consequently C's subscribers, D and F, would be bounded by C's
   choices.  If D would prefer to use route through B, and F would
   prefer to use route through E, then it was asserted that such
   policies could not be realised with BGP.










Expiration Date March 1994                                      [Page 2]

                           - 3 -



3 Solving the problem


   The problem of removing the limit of choices imposed on a subscriber
   by its direct providers can be decomposed into two orthogonal, but
   somewhat related subproblems:


       - how does a subscriber learn routes available through its
         indirect provider, if the direct provider doesn't select these
         routes

       - given that a subscriber acquires the routes available through
         its indirect provider and selects these routes, how does the
         subscriber ensure forwarding consistent with the selected
         routes.


3.1 How to acquire routes from an indirect provider


   Since BGP/IDRP operate over IP, it follows that if a subscriber has
   IP connectivity to any BGP/IDRP speaker in an indirect provider, then
   a BGP/IDRP speaker within the subscriber can establish a BGP/IDRP
   session with a BGP/IDRP speaker within the indirect provider.  The
   only needed modification to BGP/IDRP is to remove the restriction
   that external neighbors should share a common subnet.

   Alternatively one may configure a tunnel (via encapsulation) between
   a BGP/IDRP speaker within a subscriber and a BGP/IDRP speaker within
   its indirect providers. Then BGP/IDRP routing information exchange
   would flow through this tunnel and from a conceptual point of view
   the two speakers would be viewed as connected by a point-to-point
   link and thus on a common subnet. That would avoid any changes to
   BGP/IDRP.

   For the purpose of route selection and route distribution policies
   routes acquired from a BGP/IDRP speaker in the indirect provider are
   indistinguishable from the routes acquired from a direct provider.


3.2 How to provide consistent forwarding


   Providing forwarding consistent with the routes acquired from an





Expiration Date March 1994                                      [Page 3]

                           - 4 -



   indirect provider requires an additional mechanism. This is because
   routes selected by a direct provider may not be consistent with the
   routes a subscriber selected from an indirect provider. The mechanism
   should allow to hide the actual destination address, and force the
   immediate provider to use instead the address of BGP/IDRP speaker in
   the indirect provider for forwarding.

   A possible way to provide this functionality is to use encapsulation,
   where the original packet is wrapped into an envelope, with the
   destination address in the outer IP header specifying the address of
   the BGP/IDRP speaker in the indirect provider.  Any encapsulation can
   suit this purpose (e.g. [4], [5]). Alternatively one may consider
   using IP LSRR option.


3.3 Further refinements


   A BGP/IDRP speaker in the indirect provider may specify in the
   NEXT_HOP path attribute address of some other entity.  This way,
   other than the speaker entity may support encapsulation and
   forwarding.  The document constrains this entity to be within the
   same autonomous system as the speaker.

   A BGP/IDRP speaker within a subscriber may use BGP/IDRP information
   to ascertain the actual path to its BGP/IDRP peer in the indirect
   provider by using the AS_PATH/RD_PATH path attribute.  This would
   allow the speaker to refine its route selection to take into account
   not only the available routes, but also the actual path to the
   indirect provider from which the routes are acquired.


3.4 An example of operations


   We illustrate how the proposed scheme operates using the topology
   described in Section 2. Assume that C prefers routes through B to
   destinations in A, but when connectivity to B fails, C would switch
   to routes through E. C advertises these routes to both F and D. The
   routes selected by C are consistent with D's route selection policies
   (path through B as a primary, path through E as a fallback), but are
   in conflict with F's route selection policies (path through E as a
   primary, path through B as a fallback). To satisfy F's route
   selection policies a BGP/IDRP speaker in F establishes direct peering
   with a BGP/IDRP in E (E is F's indirect provider). As a result, F





Expiration Date March 1994                                      [Page 4]

                           - 5 -



   would acquire routes to destinations in A through E (directly) and
   through B (acquired from C). This information is sufficient to
   satisfy F's route selection policies.

   If the BGP/IDRP speaker in F selects a route received from the
   BGP/IDRP speaker in E, then the forwarding table entry derived from
   the route should have the next hop set to the address carried in the
   NEXT_HOP path attribute; the entry should also indicate the need for
   encapsulation.  To ensure forwarding consistent with the selected
   routes the BGP/IDRP speaker in F that peers with the BGP/IDRP speaker
   in E uses encapsulation when forwarding along the routes received
   from E. The destination address in the outer header is set to the IP
   address of the BGP/IDRP speaker in E.

   If the connection between C and E breaks, the BGP/IDRP speaker in F
   peering with the BGP/IDRP speaker in E would be able to detect this
   by examining the BGP/IDRP route to destinations in E (the new
   AS_PATH/RD_PATH will be (C, B, A, E)). Using this information the
   speaker in F would fall back on routes available through C (and B).


4 Limitations


   The proposed scheme doesn't work if a subscriber doesn't have IP
   connectivity to the indirect provider it wants to select.  On the
   other hand, it isn't clear how much sense it would make trying to
   support the ability of a subscriber to select an indirect provider to
   which the subscriber has no IP connectivity.

   While the proposed solution may be suitable to solve other problems,
   such a discussion is outside the scope of this document.
   Specifically, suitability of the proposed solution to an arbitrary
   policy-based routing problem (a.k.a. "arbitrary internet" (AI)
   problem) is outside the scope of this document.


5 Conclusions


   This document describes how the existing routing protocols (with
   optional very minor modification) combined with encapsulation can be
   used to solve the problem of indirect provider selection.  It
   provides the same dynamic rerouting capabilities as available with
   BGP/IDRP and requires no additional configuration (other than to





Expiration Date March 1994                                      [Page 5]

                           - 6 -



   optionally configure a single tunnel). The scheme doesn't require
   introduction of any new routing protocols and/or new network layer
   protocol - it is based on existing off-the-shelf components.

   The functionality provided by the scheme described in the document is
   quite similar to the "long-distance" provider selection available in
   today's telephony. The scheme may be used in similar circumstances to
   enable "long-distance" provider selection functionality in the
   Internet.

   While the scheme is described in terms of IP, it can be directly
   applicable to other existing connectionless network layer protocols,
   like CLNP.


6 Acknowledgements


   This proposal was largely stimulated by a discussion with Peter Ford
   (LANL).

   The author would like to express his deep thanks and appreciation to
   Dennis Ferguson (ANS), Dave Katz (cisco Systems), Tony Li (cisco
   Systems), and Curtis Villamizar (ANS) for their review and
   constructive comments.


References

   [1] Rekhter, Y., Li, T., `A Border Gateway Protocol 4 (BGP-4)',
   Internet Draft, April 1993

   [2] Hares, S., `IDRP for IP', Internet Draft, March 1993

   [3] Estrin, D., Steenstrup, M., "Inter-Domain Policy Routing:
   Overview of Architecture and Protocols", ACM CCR Vol 21, No 1,
   January 1991

   [4] Estrin, D., Zappala, D., Li, T., Rekhter, Y., "Source Demand
   Routing: Packet Format and Forwarding Specification (Version 1)"
   Internet Draft, September 1993

   [5] Hanks, S., Li, T., Farinacci, D., Traina, P., "Generic Routing
   Encapsulation (GRE)", Internet Draft, September 1993






Expiration Date March 1994                                      [Page 6]

                           - 7 -



Security Considerations

   Security issues are not discussed in this memo.


Author's Addresses

   Yakov Rekhter
   T.J. Watson Research Center IBM Corporation
   P.O. Box 218
   Yorktown Heights, NY 10598
   Phone:  [phone]
   email:  [e-mail]

   email: [e-mail]



































Expiration Date March 1994                                      [Page 7]